#include <vector>
#include <algorithm>
#include <string>
#include <quque>

using namespace std;

// 2389. 和有限的最长子序列
class Solution1
{
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) 
    {
        sort(nums.begin(), nums.end());
        for(int i = 1; i < nums.size(); ++i) nums[i] += nums[i - 1];
        for(int& q : queries)
        {
            q = upper_bound(nums.begin(), nums.end(), q) - nums.begin();
        }    
        return queries;
    }
};

// 2390. 从字符串中移除星号
class Solution2 
{
public:
    string removeStars(string s) 
    {
        string ret;
        for(char ch : s)
        {
            if(ch == '*') ret.pop_back();
            else ret += ch;
        }
        return ret;
    }
};

// 2197. 替换数组中的非互质数
class Solution3
{
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) 
    {
        vector<int> s;
        for(int num : nums)
        {
            s.push_back(num);
            while(s.size() > 1)
            {
                int x = s.back(), y = s[s.size() - 2];
                int g = gcd(x, y);
                if(g == 1) break;
                s.pop_back();
                s.back() *= x / g;
            }
        }
        return s;
    }
};

// 2216. 美化数组的最少删除数
class Solution4
{
public:
    int minDeletion(vector<int>& nums) 
    {
        // flag = 1 表示栈中元素的数量为奇数
        // ret 是要删除的元素的个数
        int flag = 1, last = nums[0], ret = 0;
        for(int i = 1; i < nums.size(); ++i)
        {
            if(flag)
            {
                if(nums[i] == last) ++ret;
                else flag = 0;
            }
            else
            {
                flag = 1;
                last = nums[i];
            }
        }

        return (nums.size() - ret) % 2 ? ret + 1 : ret;
    }
};

// 2273. 移除字母异位词后的结果数组
class Solution5
{
public:
    vector<string> removeAnagrams(vector<string>& words) 
    {
        vector<string> st{words[0]};
        auto cmp = [](string s1, string s2)
        {
            sort(s1.begin(), s1.end());
            sort(s2.begin(), s2.end());
            return s1 == s2;
        };

        for(int i = 1; i < words.size(); ++i)
        {
            if(!cmp(st.back(), words[i])) st.push_back(words[i]);
        }
        return st;
    }
};

// 2392. 给定条件下构造矩阵
class Solution6 
{
private:
    vector<int> topoSort(int k, vector<vector<int>>& edges)
    {
        vector<vector<int>> g(k);
        vector<int> inDeg(k);
        for(auto& e : edges)
        {
            int x = e[0] - 1, y = e[1] - 1;
            g[x].push_back(y);
            ++inDeg[y];
        }

        vector<int> order;
        queue<int> q;
        for(int i = 0; i < k; ++i)
        {
            if(inDeg[i] == 0) q.push(i);
        }

        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            order.push_back(x);
            for(int y : g[x])
            {
                if(--inDeg[y] == 0) q.push(y);
            }
        }

        return order;
    }

public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) 
    {
        auto row = topoSort(k, rowConditions), col = topoSort(k, colConditions);
        if(row.size() < k || col.size() < k) return {};
        
        vector<int> pos(k);
        for(int i = 0; i < k; ++i) pos[col[i]] = i; // 这个点放在哪一列
        vector<vector<int>> ret(k, vector<int>(k));
        for(int i = 0; i < k; ++i) ret[i][pos[row[i]]] = row[i] + 1; // 这一行该放哪一个点
        return ret;
    }
};

// 210. 课程表 II
class Solution7
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        vector<vector<int>> g(numCourses);
        vector<int> inDeg(numCourses);
        for(auto& e : prerequisites)
        {
            int x = e[1], y = e[0];
            g[x].push_back(y);
            ++inDeg[y];
        }

        vector<int> ret;
        queue<int> q;
        for(int i = 0; i < numCourses; ++i)
        {
            if(inDeg[i] == 0) q.push(i);
        }

        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            ret.push_back(x);
            for(int y : g[x])
            {
                if(--inDeg[y] == 0) q.push(y);
            }
        }

        if(ret.size() == numCourses) return ret;
        return {};
    }
};

// 2744. 最大字符串配对数目
class Solution8
{
public:
    int maximumNumberOfStringPairs(vector<string>& words) 
    {
        int ret = 0;
        bool visited[26][26]{};
        for(auto word : words)
        {
            int x = word[0] - 'a', y = word[1] - 'a';
            if(visited[y][x]) ++ret;
            else visited[x][y] = true;
        }
        return ret;
    }
};